package com.zhouyong.leetcode.将有序数组转换为二叉搜索树108;

import com.zhouyong.leetcode.TreeNode;

import java.util.Random;

/**
 * @Author 99
 * @Date 2022/10/6 13:52
 * @Version 1.0
 */
public class Test {

    // 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
    // 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过1」的二叉树。

    // 输入：nums = [-10,-3,0,5,9]
    // 输出：[0,-3,9,-10,null,5]
    // 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案

    // 输入：nums = [1,3]
    // 输出：[3,1]
    // 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

    public static void main(String[] args) {
        System.out.println(sortedArrayToBST(new int[]{-10, -3, 0, 5}));
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public static TreeNode helper(int[] nums, int left, int right) {

        // 1.中序遍历，总是选择中间位置左边的数字作为根节点
        // 终止条件
//        if (left > right) {
//            return null;
//        }
//        // 找到根节点下标
//        int num = (left + right) / 2;
//        // 判断根节点
//        TreeNode root = new TreeNode(nums[num]);
//        // 判断左孩子
//        root.left = helper(nums, left, num - 1);
//        // 判断右孩子
//        root.right = helper(nums, num + 1, right);
//        // 递归返回root
//        return root;

        // 2.中序遍历，总是选择中间位置右边的数字作为根节点
        // 终止条件
//        if (left > right) {
//            return null;
//        }
//        // 找到根节点下标
//        int num = (left + right + 1) / 2;
//        // 判断根节点
//        TreeNode root = new TreeNode(nums[num]);
//        // 判断左孩子
//        root.left = helper(nums, left, num - 1);
//        // 判断右孩子
//        root.right = helper(nums, num + 1, right);
//        // 递归返回root
//        return root;

        // 3.中序遍历，总是选择中间位置右边的数字作为根节点
        if (left > right) {
            return null;
        }
        // 选择任意一个中间位置数字作为根节点
        int num = (left + right + new Random().nextInt(2)) / 2;
        // 判断根节点
        TreeNode root = new TreeNode(nums[num]);
        // 判断左孩子
        root.left = helper(nums, left, num - 1);
        // 判断右孩子
        root.right = helper(nums, num + 1, right);
        // 递归返回root
        return root;
    }
}
